package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname LongestIncreasingSubsequence
 * @Description Leetcode 300. 最长递增子序列 中等难度 动态规划
 * @Date 2021/10/2 19:38
 * @Version 1.0
 */
public class LongestIncreasingSubsequence {


    /**
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {

        int len = nums.length;

        if (len == 1) {
            return 1;
        }

        int result = Integer.MIN_VALUE;

        int[] dp = new int[len + 1];
        dp[0] = 1;
        //dp[i]表示以i结尾的元素的最长子序列
        //状态转移方程比较难以理解
        for (int i = 1; i < len; i++) {

            //赋初值
            dp[i] = 1;

            for (int j = 0; j < i; j++) {

                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            //找出最大的子序列
            result = Math.max(dp[i], result);
        }

        return result;
    }
}
